package problems.practice;

/**
 * 1823. 找出游戏的获胜者
 * https://leetcode.cn/problems/find-the-winner-of-the-circular-game/
 *
 * @author habitplus
 * @since 2022/8/14 15:08
 */
public class T1823 {
    // 模拟 + 单循环链表
    public int findTheWinner1(int n, int k) {
        if (n < 2 || k < 1) return n;
        // 建立循环链表环
        Node hummyHead = new Node(999, null);
        Node pre = hummyHead, node;

        for (int i = 1; i <= n; ++i) {
            node = new Node(i, null);
            pre.next = node;
            pre = node;
        }

        pre.next = hummyHead.next;
        hummyHead = pre.next;

        int counter;
        for (int i = 0; i < n - 1; ++i) {
            counter = 1;
            while (counter <= k) {
                if (counter == k) {
                    pre.next = hummyHead.next;
                } else {
                    pre.next = hummyHead;
                    pre = hummyHead;
                }
                hummyHead = hummyHead.next;
                ++counter;
            }
        }

        return hummyHead.no;
    }

    static class Node {
        int no;
        Node next;

        public Node(int no, Node next) {
            this.no = no;
            this.next = next;
        }
    }

    // 数学 + 迭代
    public int findTheWinner(int n, int k) {
        int winner = 1;
        for (int i = 2; i <= n; i++) {
            winner = (k + winner - 1) % i + 1;
        }
        return winner;
    }
}
